/*
秋游中的小力和小扣设计了一个追逐游戏。他们选了秋日市集景区中的 N 个景点，景点编号为 1~N。此外，他们还选择了 N 条小路，满足任意两个景点之间都可以通过小路互相到达，且不存在两条连接景点相同的小路。整个游戏场景可视作一个无向连通图，记作二维数组 edges，数组中以 [a,b] 形式表示景点 a 与景点 b 之间有一条小路连通。

小力和小扣只能沿景点间的小路移动。小力的目标是在最快时间内追到小扣，小扣的目标是尽可能延后被小力追到的时间。游戏开始前，两人分别站在两个不同的景点 startA 和 startB。每一回合，小力先行动，小扣观察到小力的行动后再行动。小力和小扣在每回合可选择以下行动之一：

移动至相邻景点
留在原地
如果小力追到小扣（即两人于某一时刻出现在同一位置），则游戏结束。若小力可以追到小扣，请返回最少需要多少回合；若小力无法追到小扣，请返回 -1。

注意：小力和小扣一定会采取最优移动策略。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/Za25hA
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
#include <vector>
#include <iostream>
#include <set>
#include <queue>
using namespace std;
class Solution
{
public:
    int chaseGame(vector<vector<int>> &edges, int startA, int startB)
    {
        set<int> circle;
        vector<vector<int>> v;
        findCircle(edges, v, circle);
        for (int i = 0; i < v[startA].size(); i++)
        {
            if (startB == v[startA][i])
            {
                //初始a与b相邻
                return 1;
            }
        }
        // B在环中
        if (circle.size() > 3 && circle.count(startB))
        {
            return -1;
        }
        int n = edges.size();
        vector<bool> visited(n + 1, false);
        vector<int> costA(n + 1, INT_MAX);
        vector<int> costB(n + 1, INT_MAX);
        minDistance(startA, v, visited, 0, costA);
        minDistance(startB, v, visited, 0, costB);
        if (circle.size() > 3)
        {
            // B先逃到环中
            for (auto i = circle.begin(); i != circle.end(); i++)
            {
                if (costA[*i] - costB[*i] > 1)
                {
                    return -1;
                }
            }
        }
        // 计算最长追逐距离
        int ans = 0;
        for (int i = 1; i < n + 1; i++)
        {
            if (costA[i] - costB[i] > 1)
            {
                ans = max(ans, costA[i]);
            }
        }
        return ans;
    }
    // 拓扑排序找环，删除度数1的结点
    void findCircle(vector<vector<int>> &edges, vector<vector<int>> &v, set<int> &circle)
    {
        int n = edges.size();
        vector<int> count(n + 1, 0);
        v = vector<vector<int>>(n + 1, vector<int>());
        for (int i = 0; i < n; i++)
        {
            count[edges[i][0]]++;
            count[edges[i][1]]++;
            v[edges[i][0]].push_back(edges[i][1]);
            v[edges[i][1]].push_back(edges[i][0]);
        }
        for (int i = 1; i < n + 1; i++)
        {
            circle.insert(i);
        }
        vector<int> singles;
        for (int i = 0; i < n + 1; i++)
        {
            if (count[i] == 1)
            {
                singles.push_back(i);
            }
        }
        while (!singles.empty())
        {
            int e = *(singles.end() - 1);
            singles.pop_back();
            int len = v[e].size();
            for (int i = 0; i < len; i++)
            {
                count[v[e][i]]--;
                if (count[v[e][i]] == 1)
                {
                    singles.push_back(v[e][i]);
                }
            }
            circle.erase(e);
        }
    }
    //计算某一源点到其他点的最短距离
    void minDistance(int from, vector<vector<int>> &v, vector<bool> &visited, int cost, vector<int> &outCost)
    {
        if (visited[from])
        {
            return;
        }
        visited[from] = true;
        outCost[from] = min(outCost[from], cost);
        for (int i = 0; i < v[from].size(); i++)
        {
            minDistance(v[from][i], v, visited, cost + 1, outCost);
        }
        visited[from] = false;
    }
};

int main(int argc, char const *argv[])
{
    Solution s;
    // vector<vector<int>> edges = {{1, 2}, {2, 3}, {3, 4}, {4, 1}, {2, 5}, {5, 6},{6,7}};
    vector<vector<int>> edges = {{1, 2}, {2, 3}, {3, 1}, {3, 6}, {2, 4}, {4, 5}, {5, 8}, {4, 7},{8,9}};
    // vector<vector<int>> edges =
        // {{1, 2}, {2, 3}, {2, 4}, {3, 5}, {4, 6}, {5, 7}, {2, 8}, {5, 9}, {3, 10}, {5, 11}, {2, 12}, {2, 13}, {3, 14}, {8, 15}, {7, 16}, {11, 17}, {2, 18}, {5, 19}, {14, 20}, {2, 21}, {3, 22}, {18, 23}, {6, 24}, {8, 25}, {7, 26}, {16, 27}, {16, 28}, {23, 29}, {23, 30}, {5, 31}, {9, 32}, {4, 33}, {24, 34}, {7, 35}, {22, 36}, {27, 37}, {21, 38}, {13, 39}, {32, 40}, {15, 41}, {29, 42}, {35, 43}, {11, 44}, {32, 45}, {34, 46}, {3, 47}, {40, 48}, {3, 49}, {6, 50}, {1, 10}};
    cout << s.chaseGame(edges, 9, 7) << endl;
    return 0;
}
